#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    // vector<int> res;
    // bool dfs(vector<bool>& vis, vector<int>& tmp, int level)
    // {
    //     int n = vis.size();
    //     if(n == level)
    //     {
    //         if(__builtin_popcount(tmp.back() ^ 0) != 1)
    //             return false;
    //         res = tmp;
    //         return true;
    //     }
    //     for(int i = 1; i < n; i <<= 1)
    //     {
    //         int k = tmp.back() ^ i;
    //         if(!vis[k])
    //         {
    //             vis[k] = true;
    //             tmp.push_back(k);
    //             if(dfs(vis, tmp, level + 1))
    //                 return true;
    //             tmp.pop_back();
    //             vis[k] = false;
    //         }
    //     }
    //     return false;
    // }
    vector<int> grayCode(int n) {
        if (n == 0)
            return { 0 };
        else
        {
            vector<int> res = grayCode(n - 1);
            int s = res.size();
            for (int i = s - 1; i >= 0; --i)
            {
                res.push_back(res[i] | (1 << (n - 1)));
            }
            return res;
        }



        // int k = pow(2, n);
        // vector<bool> vis(k);
        // vector<int> tmp;
        // tmp.push_back(0);
        // vis[0] = true;
        // dfs(vis, tmp, 1);
        // return res;
    }
};